We study algorithmic aspects of bending wires and sheet metal into aspecified structure. Problems of this type are closely related to the questionof deciding whether a simple non-self-intersecting wire structure (acarpenter's ruler) can be straightened, a problem that was open for severalyears and has only recently been solved in the affirmative. If we impose some of the constraints that are imposed by the manufacturingprocess, we obtain quite different results. In particular, we study the variantof the carpenter's ruler problem in which there is a restriction that only onejoint can be modified at a time. For a linkage that does not self-intersect orself-touch, the recent results of Connelly et al. and Streinu imply that it canalways be straightened, modifying one joint at a time. However, we show thatfor a linkage with even a single vertex degeneracy, it becomes NP-hard todecide if it can be straightened while altering only one joint at a time. If weadd the restriction that each joint can be altered at most once, we show thatthe problem is NP-complete even without vertex degeneracies. In the special case, arising in wire forming manufacturing, that each jointcan be altered at most once, and must be done sequentially from one or bothends of the linkage, we give an efficient algorithm to determine if a linkagecan be straightened.
展开▼
